import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.*;;

public class test {
	public static String currentString;
	public static ArrayList<String> branchList;
	public static ArrayList<String> nonBranchList;
	public static int[] DFS;
	public static int[] DFSrev;
	public static int counter = 1;
	
	public static void main(String [] args) throws IOException
	{
		if(args.length == 0)
		{
			System.out.println("no args, bro");
		}
		branchList = new ArrayList<String>();
		nonBranchList = new ArrayList<String>();

		currentString = powpow(args[0]);
		
		ST pew = new ST(currentString);

		DFS = new int[currentString.length()+1]; //+1, da vi starter med insertNumber = 1;
		DFSrev = new int[currentString.length()+1]; //+1, da vi starter med insertNumber = 1;

		makeLLnew(pew.root); //TODO:lige nu får root også en LL. dette kan evt fixes.
		DFSrev();
		runStuff(pew.root);
		nonBranch(branchList);
		System.out.println("branchList.size() = "+branchList.size()+" nonBranchList.size() = "+nonBranchList.size());
	}
	
	public static void DFSrev()
	{
		for(int i = 1; i<DFSrev.length;i++)
		{
			DFSrev[DFS[i]] = i;
		}
	}
	public static void nonBranch(ArrayList<String> skillz)
	{
		String[] split = new String[3];
		int i = 1337;
		int alfa = 9001;
		for(int g = 0;g<skillz.size();g++)
		{
			boolean runz = true;
			split = skillz.get(g).split(",");
			i = Integer.parseInt(split[0].substring(1));
			alfa = Integer.parseInt(split[1]);

			if(i > 0 && currentString.charAt(i+alfa-1) == currentString.charAt(i-1)) //if a = S[i-1]. i>0, da i-1 ellers ville give out of bounds. jeg bruger &&(lazy), da den kun skal evaluere anden del, hvis i faktisk er over 0.
			{
				nonBranchList.add("("+(i-1)+","+alfa+",2)");
				//this process, called the rotation procedure, is continued to the left until an inqeuality is observed, at which point the procedure stops.
				int stepsLeft = 1;
				while(runz)
				{
					if(i+alfa-1-stepsLeft < 0 | i-1-stepsLeft < 0) //hvis en af dem bliver under 0, skal den ikke køre løkken mere.
					{
						runz = false;
					}
					else if( currentString.charAt(i+alfa-1-stepsLeft) == currentString.charAt(i-1-stepsLeft) ) //stepsLeft er hvor mange pladser til venstre vi er rykket.
					{
						nonBranchList.add("("+(i-1-stepsLeft)+","+alfa+",2)");
						stepsLeft++;
					}
					else
					{
						runz = false;
					}
				}
			}
		}
	}
	
	public static void makeLLnew(Node n)
	{
		n.dfsAssign[0] = counter;
		if(n.amountOfChildren() == 0)
		{
			DFS[n.getInsertNumber()] = counter;
			counter++;
		}
		else
		{
			for(int i =0; i<n.amountOfChildren();i++)
			{
				makeLLnew(n.cList.get(i));	
			}
		}
			//her går jeg ud af min recursion igen, så jeg skal sætte den anden del af min dfsassign. Jeg skal dog huske at trække 1 fra counter, da jeg har talt den op, efter jeg var nede i noden
			n.dfsAssign[1] = counter - 1;
		}

	public static void runStuff(Node n)
	{
		if(n.amountOfChildren() == 0) //if leaf
		{
			return;
		}
		for(int i = 0;i<n.amountOfChildren();i++)
		{
			if(!(n.marked == true))
			{
				rest(n);
			}
			runStuff(n.cList.get(i));
		}
	}
	
	public static void rest(Node n)
	{
		//2a: collect the list LL'(n) for n.
		Node biggestChild = n.cList.get(0);
		if(n.amountOfChildren() > 1)
		{
			for(int i = 0;i<n.amountOfChildren();i++)
			{
				if(biggestChild.dfsAssign[1]-biggestChild.dfsAssign[0] < n.cList.get(i).dfsAssign[1]-n.cList.get(i).dfsAssign[0])
				{
					biggestChild = n.cList.get(i);
				}
			}
		}
		int Dv = n.getTotalString().length();

		int j = 0;
		int i = 0;
		//hence to determine if a leaf j = i + D(v) is in LL(v) just  check if DFS[j] is between the two dfs numbers recorded at v
		//for all leaves i in LL'(v), test if j = i + D(v) is in LL(v). D(v) = |L(v)| aka. længden af strengen gemt i v.
		//2b: test whether leaf j = i + D(v) is in LL(v)
		for(int h = n.dfsAssign[0];h<=n.dfsAssign[1];h++) //jeg kører så mange gange, som der er dfs numre i min node. Jeg starter med h = n.dfsAssign[0], så min løkke kører i intervallet der er dfs på den node jeg kigger på. På denne måde, kan jeg nemt sortere biggestChild fra. husk at den skal være <= !!!
		{
			if(h >= biggestChild.dfsAssign[0] && h <= biggestChild.dfsAssign[1]) //hvis det tal jeg kigger på atm, også ligger i biggest child, skal jeg bare continue.
			{
				continue;
			}
			//2b part 1
			i = DFSrev[h]; //i er det leaf der tilsvarer min DFS værdi. Denne kan jeg slå op i DFSrev
			j = i + Dv; //j = i + D(v)
			if(DFS[j] >= n.dfsAssign[0] & DFS[j] <= n.dfsAssign[1])
			{
				//2b part 2: test whether S[i] != S[i+2D(v)|. If true, theres a brancing tandem repeat of length 2D(v) starting at position i.
				if(currentString.charAt(i-1) != currentString.charAt(i-1+(2*Dv)))
				{
					String ret2b = "("+(i-1)+","+Dv+",2)";
					branchList.add(ret2b);
				}
			}
			//2c
			j = DFSrev[h]; //j er det leaf der tilsvarer min DFS værdi. Denne kan jeg slå op i DFSrev
			i = j - Dv;
			if(i <= 0)
			{
				continue;
			}
			if(DFS[i] >= biggestChild.dfsAssign[0] & DFS[i] <= biggestChild.dfsAssign[1])// jeg husker at bruge i her, da man tjekker på leafet.
			{
				String ret2c = "("+(i-1)+","+Dv+",2)"; //i-1 da jeg skal slå op i noget hvor man starter på index 0
				branchList.add(ret2c);
			}
			else if(DFS[i] >= biggestChild.dfsNumber & DFS[i] <= biggestChild.dfsNumber)
			{
				String ret2c = "("+(i-1)+","+Dv+",2)"; //i-1 da jeg skal slå op i noget hvor man starter på index 0
				branchList.add(ret2c);
			}
		}
		n.marked = true;
	}
	
	public static String powpow(String argString) throws IOException
	{
		String fileString = "..//files/"+argString;
		File f = new File(fileString);
		InputStream in = new FileInputStream(f);
		int b;
		char s;
		String output = "";
		while((b = in.read()) != -1)
		{
			s = (char)b;
			if(b != 13) //jeg vil ikke have linieskift med
			{
			output = output + s;
			}
		}

		in.close();
		if( !(output.endsWith("$")) )
		{
			output = output + "$";
		}
		return output;
	}
}